// -*- coding: utf-8 -*-
/**
 * Project: AlgorithmsLearn
 *
 * @author: yanking
 * Create time: 2022-03-25 20:53
 * IDE: IntelliJ IDEA
 * Introduction:
 */
package com.LeetCodeT.ArraysTrain.preFixTrain;


public class MaxSumOfThreeSubarrays {
    /**
     * 计算三个无重叠子数组的最大和
     * 序列DP + 前缀和
     *
     * @param nums
     * @param k
     * @return
     */
    public int[] maxSumOfThreeSubarraysT(int[] nums, int k) {
        int n = nums.length;
        if (3 * k > n) {
            return new int[]{};
        }
        reverse(nums);
        /*-----构造前缀和数组-----*/
        int[] sum = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            sum[i] = sum[i - 1] + nums[i - 1];
        }
        /*-----匹配前缀和最大的三个无重叠的子数组-----*/
        /*
            状态转移记录当前元素的变量-> 增加维度
                f[i][j]: 第i个元素，作为三个子数组的第j个子数组
         */
        int[][] f = new int[n + 1][4];
        for (int i = k; i < n + 1; i++) {
            for (int j = 1; j < 4; j++) {
                f[i][j] = Math.max(f[i - 1][j], f[i - k][j - 1] + sum[i] - sum[i - k]);
            }
        }
        int[] ans = new int[3];
        int i = n, j = 3, idx = 0;
        while (j > 0) {
            if (f[i - 1][j] > f[i - k][j - 1] + sum[i] - sum[i - k]) {
                i--;
            } else {
                ans[idx++] = n - i;
                i -= k;
                j--;
            }

        }
        return ans;

    }

    /**
     * 倒转数组
     *
     * @param nums
     */
    private void reverse(int[] nums) {
        int l = 0, r = nums.length - 1;
        while (l < r) {
            int t = nums[l];
            nums[l] = nums[r];
            nums[r] = t;
            l--;
            r++;
        }
    }


    /**
     * 逆序DP:从较小的字典序开始寻找
     *
     * @param nums
     * @param k
     * @return
     */
    public int[] maxSumOfThreeSubarrays(int[] nums, int k) {
        /*-----构建前缀和数组-----*/
        int n = nums.length;
        int[] sum = new int[n + 1];
        for (int i = 1; i < n + 1; i++) {
            sum[i] = sum[i - 1] + nums[i - 1];
        }
        /*-----构建状态数组-----*/
        int[][] f = new int[n + 2][4];
        for (int i = n - k + 1; i >= 1; i--) {
            for (int j = 1; j < 4; j++) {
                f[i][j] = Math.max(f[i + 1][j], f[i + k][j - 1] + sum[i + k - 1] - sum[i - 1]);
            }
        }
        int[] ans = new int[3];
        int idx = 0, j = 3, i = 1;
        while (j > 0) {
            if (f[i + 1][j] > f[i + k][j - 1] + sum[i + k - 1] - sum[i - 1]) {
                i++;
            } else {
                ans[idx++] = i - 1;
                i += k;
                j--;
            }
        }

        return ans;
    }
}
